Lemonade change [Simulation]¶
Time: O(N); Space: O(1); easy
At a lemonade stand, each lemonade costs \$5. Customers are standing in a queue to buy from you, and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a \$5, \$10, or \$20 bill. You must provide the correct change to each customer, so that the net transaction is that the customer pays \$5. Note that you don’t have any change in hand at first.
Return true if and only if you can provide every customer with correct change.
Example 1:
Input: bills = [5,5,5,10,20]
Output: True
Explanation:
From the first 3 customers, we collect three \$5 bills in order.
From the fourth customer, we collect a \$10 bill and give back a \$5.
From the fifth customer, we give a \$10 bill and a \$5 bill.
Since all customers got correct change, we output true.
Example 2:
Input: bills = [5,5,10]
Output: True
Example 3:
Input: bills = [10,10]
Output: False
Example 4:
Input: bills = [5,5,10,10,20]
Output: False
Explanation:
From the first two customers in order, we collect two \$5 bills.
For the next two customers in order, we collect a \$10 bill and give back a \$5 bill.
For the last customer, we can’t give change of \$15 back because we only have two $10 bills.
Since not every customer received correct change, the answer is false.
Notes:
0 <= bills.length <= 10000
bills[i] will be either 5, 10, or 20.
Intuition and Algorithm Let’s try to simulate giving change to each customer buying lemonade. Initially, we start with no five dollar bills, and no ten dollar bills. If a customer brings a \$5 bill, then we take it. If a customer brings a \$10 bill, we must return a five dollar bill. If we don’t have a five dollar bill, the answer is False, since we can’t make correct change. If a customer brings a \$20 bill, we must return \$15. If we have a \$10 and a \$5, then we always prefer giving change in that, because it is strictly worse for making change than three \$5 bills. Otherwise, if we have three \$5 bills, then we’ll give that. Otherwise, we won’t be able to give \$15 in change, and the answer is False.
[1]:
class Solution1(object):
def lemonadeChange(self, bills) -> bool:
"""
:type bills: List[int]
:rtype: bool
"""
five = ten = 0
for bill in bills:
if bill == 5:
five += 1
elif bill == 10:
if not five:
return False
five -= 1
ten += 1
else:
if ten and five:
ten -= 1
five -= 1
elif five >= 3:
five -= 3
else:
return False
return True
[2]:
s = Solution1()
bills = [5,5,5,10,20]
assert s.lemonadeChange(bills) == True
bills = [5,5,10]
assert s.lemonadeChange(bills) == True
bills = [10,10]
assert s.lemonadeChange(bills) == False
bills = [5,5,10,10,20]
assert s.lemonadeChange(bills) == False
[3]:
import collections
class Solution2(object):
def lemonadeChange(self, bills) -> bool:
"""
:type bills: List[int]
:rtype: bool
"""
coins = [20, 10, 5]
counts = collections.defaultdict(int)
for bill in bills:
counts[bill] += 1
change = bill - coins[-1]
for coin in coins:
if change == 0:
break
if change >= coin:
count = min(counts[coin], change//coin)
counts[coin] -= count
change -= coin * count
if change != 0:
return False
return True
[4]:
s = Solution2()
bills = [5,5,5,10,20]
assert s.lemonadeChange(bills) == True
bills = [5,5,10]
assert s.lemonadeChange(bills) == True
bills = [10,10]
assert s.lemonadeChange(bills) == False
bills = [5,5,10,10,20]
assert s.lemonadeChange(bills) == False